/**
 * 
 */
package leetCode;

/**
 * @author zhongfang
 *
 */
public class ValidParenthesisString {
	public boolean checkValidString(String s, int i, int leftCount) {
		if (i == s.length()) {
			return leftCount == 0;
		}
		if (s.charAt(i) == '*') {
			boolean res = checkValidString(s, i + 1, leftCount) || checkValidString(s, i + 1, leftCount + 1);
			if (res == false && leftCount != 0) {
				res = checkValidString(s, i + 1, leftCount - 1);
			}
			return res;
		} else if (s.charAt(i) == '(') {
			return checkValidString(s, i + 1, leftCount + 1);
		} else {
			if (leftCount == 0) {
				return false;
			}
			return checkValidString(s, i + 1, leftCount - 1);
		}
	}

	public boolean checkValidStringDP(String s) {
		int n = s.length();
		boolean[] dp = new boolean[n + 1];
		dp[0] = true;
		for (int i = n - 1; i >= 0; i--) {
			boolean[] tmp = new boolean[n + 1];
			for (int j = 0; j <= i; j++) {// 左括号个数
				char ch = s.charAt(i);
				if (ch == '(') {
					tmp[j] = dp[j + 1];
				} else if (ch == ')') {
					tmp[j] = j != 0 ? dp[j - 1] : false;
				} else {
					tmp[j] = dp[j] || dp[j + 1] || (j != 0 ? dp[j - 1] : false);
				}
			}
			dp = tmp;
		}
		return dp[0];
	}

	/**
	 * 暴力解法
	 * 
	 * @param s
	 * @return
	 */
	public boolean checkValidString(String s) {
		return checkValidString(s, 0, 0);
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println(new ValidParenthesisString().checkValidStringDP("(*))"));
	}

}
